package job.kedaxunfei;

import java.util.Scanner;

/**
 * @author wq
 * 题目描述：https://blog.csdn.net/qq_35885429/article/details/107719845
 */
public class SortSequence {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scanner.nextInt();
        }
        new SortSequence().quickSort(arr,0,n-1);
        for (int e:arr
             ) {
            System.out.print(e+" ");
        }
    }
    public  void quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }

        int i=left,j=right,base,temp;
        base=arr[left];
        while(i<j){
            while(arr[j]>=base&&i<j){
                j--;
            }
            while(arr[i]<=base&&i<j){
                i++;
            }

            if(i<j){
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }

        //基准数归位
        arr[left]=arr[i];
        arr[i]=base;
        for(int e:arr){
            System.out.print(e+" ");
        }
        System.out.println();
        quickSort(arr,left,i-1);//递归左边
        quickSort(arr,i+1,right);//递归右边
    }
}

